#include <qapplication.h>
#include "defs.H"
#include "G_matrix.H"
#include "G_ref.H"
#include "G_refs.H"
#include "G_object.H"
#include "my_hash_map.H"
#include <vector>


class edge
{
public:
    static G_matrix identity;
    G_ref *ref;
    edge(G_ref *inRef)
    {
        ref = inRef;
    }

    virtual const G_matrix &getMatrix() const { return identity; }
};

G_matrix edge::identity = G_matrix();


class matrixEdge : public edge
{
public:
    G_matrix m;

    matrixEdge(G_ref *inRef, G_matrix inM) : edge(inRef), m(inM) {}

    const G_matrix &getMatrix() const { return m; }
};


// This class stores the graph of dependencies between objects.
// A constraint like:
// "If Point P moves by vector V, Segment S must move by the vector
//  M * V" would be represented by two matrixEdge's of M and M^-1
// between P and S.  If a bunch of edges form a cycle such that
// the product of matrices around that cycle is not the identity,
// that graph is inconsistent and needs to be repaired.  Since fixed
// edges are always associated with the identity matrix, a graph
// only containing fixed edges is always consistent.

class mygraph
{
private:
    hash_map<G_ref *, vector<edge *> > map1;
    vector<vector<pair<G_ref *, edge *> > > changeableEdges;

public:
    void createFixedEdge(G_ref *r1, G_ref *r2)
    {
        map1[r1].push_back(new edge(r2));
        map1[r2].push_back(new edge(r1));
    }

    hash_map<G_ref *, G_matrix> getOutput(G_ref *initial)
    {
        hash_map<G_ref *, G_matrix> m; //will be returned
        //walks through the graph via bfs and multiplies the matrices through

        hash_set<G_ref *> visited;
        vector<pair<G_ref *, G_matrix> > toVisit;

        toVisit.push_back(make_pair(initial, G_matrix()));
        visited.insert(initial);

        int i = 0;
        while(i < (int)toVisit.size())
        {
            int j = 0;
            if(toVisit[i].first->getParents().size() == 0 &&
                toVisit[i].second * G_point(0, 0) == G_point(0, 0))
            {
                if((toVisit[i].first->getType() & G_TEXT) == 0) m[toVisit[i].first] = toVisit[i].second;
            }

            while(j < (int)(map1[toVisit[i].first].size()))
            {
                edge *e = (map1[toVisit[i].first])[j];

                if(visited.count(e->ref) == 0)
                {
                    visited.insert(e->ref);
                    toVisit.push_back(make_pair(e->ref, e->getMatrix() * toVisit[i].second));
                }

            j++;
            }
            i++;
        }
        return m;
    }

    G_matrix getPath(G_ref *r1, G_ref *r2)
    {
        hash_set<G_ref *> visited;
        vector<pair<G_ref *, G_matrix> > toVisit;

        toVisit.push_back(make_pair(r1, G_matrix()));
        visited.insert(r1);

        if(r1 == r2) return G_matrix();

        int i = 0;

        while(i < (int)toVisit.size())
        {
            int j = 0;

            while(j < (int)map1[toVisit[i].first].size())
            {
                edge *e = (map1[toVisit[i].first])[j];
                if(e->ref == r2) return e->getMatrix() * toVisit[i].second;

                if(visited.count(e->ref) == 0)
                {
                    visited.insert(e->ref);
                    toVisit.push_back(make_pair(e->ref, e->getMatrix() * toVisit[i].second));
                }
            j++;
            }

            i++;
        }

        return G_matrix::getNullMatrix();
    }


    bool createChangeableEdge(G_ref *r1, G_ref *r2, G_matrix forw, G_matrix rev, int level)
    {
        G_matrix m = getPath(r1, r2);

        if(!(m == G_matrix::getNullMatrix()))  //check validity
        {
            if(m.almostEqual(forw) == false) return false;
        }

        if(r1 == r2) return true;

        edge *e1 = new matrixEdge(r2, forw);
        edge *e2 = new matrixEdge(r1, rev);

        map1[r1].push_back(e1);
        map1[r2].push_back(e2);

        if(level >= (int)changeableEdges.size()) changeableEdges.resize(level + 1);

        changeableEdges[level].push_back(make_pair(r1, e1));
        changeableEdges[level].push_back(make_pair(r2, e2));

        return true;
    }


    void clear() //resets everything:
    {
        map1.clear();
        changeableEdges.clear();
    }

    void clearLevel(int level)
    {
        int i;

        if(level >= (int)changeableEdges.size()) return;

        for(i = 0; i < (int)changeableEdges[level].size(); ++i)
        {
            G_ref *r = changeableEdges[level][i].first;
            edge *e = changeableEdges[level][i].second;

            map1[r].erase(find(map1[r].begin(), map1[r].end(), e));
        }

        changeableEdges[level].clear();
    }

};


static mygraph graph1;

bool setupFixedRef(G_ref *ref);
int setupChangeableRef(G_ref *ref, int state, int level);
void setupFixedChangeableRef(G_ref *ref); // for going back in case of timeout

static hash_set<G_ref *> done;
static G_refs changeable;
static G_ref *startRef;

// This function sets up the parts of the graph that
// will definitely not change.  It is linear time.
void BuildReverseFixed(G_ref *ref)
{
    if(done.count(ref) > 0) return; //already done.
    done.insert(ref);

    if(setupFixedRef(ref)) changeable.push_back(ref);

    int i;
    for(i = 0; i < (int)ref->getParents().size(); ++i)
    {
        BuildReverseFixed(ref->getParents()[i]);
    }
}

// This function tries to set up a consistent set
// of edges among those that can change.  It does
// it with a simple exponential-time (in the
// number of changeable edges) brute-force
// algorithm, but if it finds it is taking too
// long, it reverts to a simpler linear-time
// algorithm which will potentially make more
// objects move than necessary.
void BuildReverseChangeable()
{
    int i;

    bool timeOut = false;

    vector<int> states;
  
    QTime t;
  
    t.start();

    i = 0;
    while(i < (int)changeable.size())
    {
        if(t.elapsed() > 1000)
        {
            //TIMEOUT!  go back to fixed algorithm.
            timeOut = true;
            break;
        }

        if((int)states.size() <= i) states.push_back(0);
    
        int result = setupChangeableRef(changeable[i], states[i], i);
    
        if(result)
        {
            states[i] = result;
            i++;
        }
        else
        {
            graph1.clearLevel(i);
            states.pop_back();
            i--;
        }
    }

    if(!timeOut) return;

    while(i >= 0)
    {
        graph1.clearLevel(i);
        i--;
    }

    for(i = 0; i < (int)changeable.size(); ++i)
    {
        setupFixedChangeableRef(changeable[i]);
    }
}

// This is the main function.
// It first sets up the part of the graph
// that's fixed, then the part of the graph
// that's variable, taking care of special
// cases, such as constrained points and text
// objects in the process.
hash_map<G_ref *, G_matrix> BuildReverse(const G_refs &refs)
{
    int i;

    done.clear();
    graph1.clear();
    changeable.clear();

    if(refs.size() == 0) return hash_map<G_ref *, G_matrix>();

    //check if the input consists of a single constrained point
    if(refs.size() == 1 && refs[0]->getType() == G_POINT &&
       refs[0]->getDescendType() == G_CONSTRAINED_POINT)
    {
      hash_map<G_ref *, G_matrix> out;
      out[refs[0]] = G_matrix();
      return out;
    }

    G_refs texts, refs2;

    //separate the texts (which have no impact on the structure)
    //from the refs
    for(i = 0; i < (int)refs.size(); ++i)
    {
        if(refs[i]->getType() & G_TEXT)
        {
            texts.push_back(refs[i]);
        }
        else
        {
            refs2.push_back(refs[i]);
        }
    }

    if(refs2.size() > 0)
    {
        startRef = refs2[0];

        for(i = 0; i < (int)refs2.size() - 1; ++i)
        {
            graph1.createFixedEdge(refs2[i], refs2[i + 1]);
        }

        for(i = 0; i < (int)refs2.size(); ++i)
        {
            BuildReverseFixed(refs2[i]);
        }

        BuildReverseChangeable();

        hash_map<G_ref *, G_matrix> toBeReturned = graph1.getOutput(refs2[0]);

        for(i = 0; i < (int)texts.size(); ++i)
        {
            toBeReturned[texts[i]] = G_matrix();
        }

        return toBeReturned;
    }

  //else if only texts are present

    hash_map<G_ref *, G_matrix> toBeReturned;

    for(i = 0; i < (int)texts.size(); ++i)
    {
        toBeReturned[texts[i]] = G_matrix();
    }

    return toBeReturned;
}

bool setupFixedRef(G_ref *ref) //returns whether there are changeable edges for it
{
    if(ref->getParents().size() == 0) return false;
  
    if(ref->getType() & G_GEOMETRIC && IS_TRANSFORM(ref->getDescendType()))
    {
        if(ref->getDescendType() == G_TRANSLATED)
        {
            graph1.createFixedEdge(ref, ref->getParents()[0]);
            graph1.createFixedEdge(ref->getParents()[1], ref->getParents()[2]);
        }
        else if(ref->getDescendType() == G_ROTATED)
        {
            if(ref->getParents().count() == 5)
            { //by three points
                graph1.createFixedEdge(ref->getParents()[2], ref->getParents()[3]);
                graph1.createFixedEdge(ref->getParents()[2], ref->getParents()[4]);
            }
            return true;
        }
        else if(ref->getDescendType() == G_SCALED)
        {
            return true;
        }
        else if(ref->getDescendType() == G_REFLECTED)
        {
            return true;
        }
    }
    else if(ref->getType() == G_CIRCLE && ref->getDescendType() == G_CENTERRADIUS_CIRCLE)
    {
        graph1.createFixedEdge(ref, ref->getParents()[0]);
    }
    else if(ref->getType() == G_LINE && (ref->getDescendType() == G_PARALLEL_LINE ||
                                       ref->getDescendType() == G_PERPENDICULAR_LINE))
    {
        graph1.createFixedEdge(ref, ref->getParents()[0]);
    }
    else if(ref->getType() == G_LOCUS)
    {
        graph1.createFixedEdge(ref, ref->getParents()[0]);
        graph1.createFixedEdge(ref, ref->getParents()[1]);
    }
    else if(ref->getType() & G_TEXT)
    {
        int i;

        if(ref->getType() == G_MEASURE &&
       (ref->getDescendType() == G_DISTANCE_MEASURE ||
        ref->getDescendType() == G_ANGLE_MEASURE))
        { //these have dependent parents
            for(i = 0; i < (int)ref->getParents().size() - 1; ++i)
            {
                graph1.createFixedEdge(ref->getParents()[i + 1], ref->getParents()[i]);
            }
        }
    }
    else
    {
        int i;
        for(i = 0; i < (int)ref->getParents().size(); ++i)
        {
        graph1.createFixedEdge(ref, ref->getParents()[i]);
        }
    }

    return false;
}


void setupFixedChangeableRef(G_ref *ref)
{
    //this works for all--rotated, translated, scaled.
    graph1.createFixedEdge(ref, ref->getParents()[0]);
    graph1.createFixedEdge(ref, ref->getParents()[1]);
}


int setupChangeableRef(G_ref *ref, int state, int level)
{
    bool success;

    graph1.clearLevel(level);
  
    if(ref->getDescendType() == G_ROTATED)
    {

        if(state < 1)
        {
            double angle;

            if(ref->getParents().count() == 5)
            { //by three points
                angle = (ref->getParents()[4]->getObject()->getPoint() -
                ref->getParents()[3]->getObject()->getPoint()).angle() -
                (ref->getParents()[2]->getObject()->getPoint() -
            ref->getParents()[3]->getObject()->getPoint()).angle();
            }
            else
            { //value-based
                angle = ref->getParents()[2]->getObject()->getNumValue() / -180. * M_PI;
            }

            success = graph1.createChangeableEdge(ref, ref->getParents()[0], G_matrix::rotate(angle),
					    G_matrix::rotate(-angle), level);
            success = success && graph1.createChangeableEdge(startRef, ref->getParents()[1],
						      G_matrix::translate(1,1), G_matrix::translate(-1,-1),
						      level);
      
            if(success) return 1;
      
            graph1.clearLevel(level);
        }

        if(state < 2)
        {
            success = graph1.createChangeableEdge(ref, ref->getParents()[0], G_matrix(), G_matrix(), level);
            success = success && graph1.createChangeableEdge(ref, ref->getParents()[1],
						       G_matrix(), G_matrix(), level);
      
            if(success) return 2;
      
            graph1.clearLevel(level);
        }
    
        return 0;
    }

    if(ref->getDescendType() == G_SCALED)
    {
        if(state < 1)
        {
            double scale;

            if(ref->getParents().count() == 4)
            { //by two segments
                scale = ref->getParents()[3]->getObject()->getSegment().length() /
                ref->getParents()[2]->getObject()->getSegment().length();
            }
            else
            { //value based
                scale = ref->getParents()[2]->getObject()->getNumValue();
            }

            success = graph1.createChangeableEdge(ref, ref->getParents()[0], G_matrix::scale(1. / (scale + SMALL)),
					    G_matrix::rotate(scale), level);
            success = success && graph1.createChangeableEdge(startRef, ref->getParents()[1],
						      G_matrix::translate(1,1), G_matrix::translate(-1,-1),
						      level);
      
            if(success) return 1;
      
            graph1.clearLevel(level);
        }

        if(state < 2)
        {
            success = graph1.createChangeableEdge(ref, ref->getParents()[0], G_matrix(), G_matrix(), level);
            success = success && graph1.createChangeableEdge(ref, ref->getParents()[1],
						       G_matrix(), G_matrix(), level);
      
            if(success) return 2;
      
            graph1.clearLevel(level);
        }
    
        return 0;
  }

    if(ref->getDescendType() == G_REFLECTED)
    {
        if(state < 1)
        {
            G_straight *reflect = ref->getParents()[1]->getObject()->getStraightRef();
            G_matrix m = G_matrix::reflect(reflect->getDirection().getX(),
				     reflect->getDirection().getY());

            success = graph1.createChangeableEdge(ref, ref->getParents()[0], m, m, level);
            success = success && graph1.createChangeableEdge(startRef, ref->getParents()[1],
						      G_matrix::translate(1,1), G_matrix::translate(-1,-1),
						      level);
      
            if(success) return 1;
      
            graph1.clearLevel(level);
        }

        if(state < 2)
        {
            success = graph1.createChangeableEdge(ref, ref->getParents()[0], G_matrix(), G_matrix(), level);
            success = success && graph1.createChangeableEdge(ref, ref->getParents()[1],
						       G_matrix(), G_matrix(), level);
            if(success) return 2;
            graph1.clearLevel(level);
        }
    
        return 0;
    }

  return 0;
}
